{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Boundary of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: boundaryOfBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的边界"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二叉树的 <strong>边界</strong> 是由 <strong>根节点 </strong>、<strong>左边界</strong> 、按从左到右顺序的<strong> 叶节点</strong> 和 <strong>逆序的右边界</strong> ，按顺序依次连接组成。</p>\n",
    "\n",
    "<p><strong>左边界 </strong>是满足下述定义的节点集合：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>根节点的左子节点在左边界中。如果根节点不含左子节点，那么左边界就为 <strong>空</strong> 。</li>\n",
    "\t<li>如果一个节点在左边界中，并且该节点有左子节点，那么它的左子节点也在左边界中。</li>\n",
    "\t<li>如果一个节点在左边界中，并且该节点 <strong>不含</strong> 左子节点，那么它的右子节点就在左边界中。</li>\n",
    "\t<li>最左侧的叶节点 <strong>不在</strong> 左边界中。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>右边界</strong> 定义方式与 <strong>左边界</strong> 相同，只是将左替换成右。即，右边界是根节点右子树的右侧部分；叶节点 <strong>不是</strong> 右边界的组成部分；如果根节点不含右子节点，那么右边界为 <strong>空</strong> 。</p>\n",
    "\n",
    "<p><strong>叶节点</strong> 是没有任何子节点的节点。对于此问题，根节点 <strong>不是</strong> 叶节点。</p>\n",
    "\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，按顺序返回组成二叉树 <strong>边界</strong> 的这些值。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/11/boundary1.jpg\" style=\"width: 299px; height: 290px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3,4]\n",
    "<strong>输出：</strong>[1,3,4,2]\n",
    "<b>解释：</b>\n",
    "- 左边界为空，因为二叉树不含左子节点。\n",
    "- 右边界是 [2] 。从根节点的右子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以右边界只有 2 。\n",
    "- 叶节点从左到右是 [3,4] 。\n",
    "按题目要求依序连接得到结果 [1] + [] + [3,4] + [2] = [1,3,4,2] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/11/boundary2.jpg\" style=\"width: 599px; height: 411px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6,null,null,null,7,8,9,10]\n",
    "<strong>输出：</strong>[1,2,4,7,8,9,10,6,3]\n",
    "<b>解释：</b>\n",
    "- 左边界为 [2] 。从根节点的左子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以左边界只有 2 。\n",
    "- 右边界是 [3,6] ，逆序为 [6,3] 。从根节点的右子节点开始的路径为 3 -> 6 -> 10 ，但 10 是叶节点。\n",
    "- 叶节点从左到右是 [4,7,8,9,10]\n",
    "按题目要求依序连接得到结果 [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3] 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 <= Node.val <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [boundary-of-binary-tree](https://leetcode.cn/problems/boundary-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [boundary-of-binary-tree](https://leetcode.cn/problems/boundary-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,3,4]', '[1,2,3,4,5,6,null,null,null,7,8,9,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        elif root.left is None and root.right is None:\n",
    "            return [root.val]\n",
    "        \n",
    "        rlefts = []\n",
    "        rrights = []\n",
    "        rleaves = []\n",
    "\n",
    "        # find left boundary\n",
    "        leftb = root.left\n",
    "        while leftb and (leftb.left or leftb.right):\n",
    "            rlefts.append(leftb.val)\n",
    "            if leftb.left:\n",
    "                leftb = leftb.left\n",
    "            else:\n",
    "                leftb = leftb.right\n",
    "        \n",
    "        # find right boundary\n",
    "        rightb = root.right\n",
    "        while rightb and (rightb.left or rightb.right):\n",
    "            rrights.append(rightb.val)\n",
    "            if rightb.right:\n",
    "                rightb = rightb.right\n",
    "            else:\n",
    "                rightb = rightb.left\n",
    "\n",
    "        # find leaves\n",
    "        stk = [root]\n",
    "        while stk:\n",
    "            node = stk.pop()\n",
    "            if node.left is None and node.right is None:\n",
    "                rleaves.append(node.val)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    stk.append(node.left)\n",
    "                if node.right:\n",
    "                    stk.append(node.right)\n",
    "\n",
    "        return [root.val] + rlefts + rleaves[::-1] + rrights[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        elif root.left is None and root.right is None:\n",
    "            return [root.val]\n",
    "        \n",
    "        rlefts = []\n",
    "        rrights = []\n",
    "        rleaves = []\n",
    "\n",
    "        leftb = root.left   # left boundary\n",
    "        while leftb and (leftb.left or leftb.right):\n",
    "            rlefts.append(leftb.val)\n",
    "            if leftb.left:\n",
    "                leftb = leftb.left\n",
    "            else:\n",
    "                leftb = leftb.right\n",
    "        \n",
    "        rightb = root.right  # right boundary\n",
    "        while rightb and (rightb.left or rightb.right):\n",
    "            rrights.append(rightb.val)\n",
    "            if rightb.right:\n",
    "                rightb = rightb.right\n",
    "            else:\n",
    "                rightb = rightb.left\n",
    "\n",
    "\n",
    "        stk = [root]\n",
    "        while stk:\n",
    "            node = stk.pop()\n",
    "            if node.left is None and node.right is None:\n",
    "                rleaves.append(node.val)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    stk.append(node.left)\n",
    "                if node.right:\n",
    "                    stk.append(node.right)\n",
    "\n",
    "        return [root.val] + rlefts + rleaves[::-1] + rrights[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "  def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "    if not root.left and not root.right:  return [root.val]\n",
    "    leftBound = [root.val]\n",
    "    cur = root.left\n",
    "    while cur:\n",
    "      leftBound.append(cur.val)\n",
    "      if cur.left:  cur = cur.left\n",
    "      elif cur.right: cur = cur.right\n",
    "      else: \n",
    "        leftBound.pop()\n",
    "        break\n",
    "\n",
    "    stack = [root]\n",
    "    while stack:\n",
    "      cur = stack.pop()\n",
    "      if not cur.left:\n",
    "        if not cur.right: leftBound.append(cur.val)\n",
    "        else: stack.append(cur.right)\n",
    "      elif not cur.right: stack.append(cur.left)\n",
    "      else: stack.extend([cur.right, cur.left])\n",
    "\n",
    "    rightBound = []\n",
    "    cur = root.right\n",
    "    while cur:\n",
    "      rightBound.append(cur.val)\n",
    "      if cur.right:  cur = cur.right\n",
    "      elif cur.left: cur = cur.left\n",
    "      else: \n",
    "        rightBound.pop()\n",
    "        break\n",
    "    return leftBound + rightBound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "  def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "    if not root.left and not root.right:  return [root.val]\n",
    "    leftBound = [root.val]\n",
    "    cur = root.left\n",
    "    while cur:\n",
    "      leftBound.append(cur.val)\n",
    "      if cur.left:  cur = cur.left\n",
    "      elif cur.right: cur = cur.right\n",
    "      else: \n",
    "        leftBound.pop()\n",
    "        break\n",
    "\n",
    "    stack = [root]\n",
    "    while stack:\n",
    "      cur = stack.pop()\n",
    "      if not cur.left:\n",
    "        if not cur.right: leftBound.append(cur.val)\n",
    "        else: stack.append(cur.right)\n",
    "      elif not cur.right: stack.append(cur.left)\n",
    "      else: stack.extend([cur.right, cur.left])\n",
    "\n",
    "    rightBound = []\n",
    "    cur = root.right\n",
    "    while cur:\n",
    "      rightBound.append(cur.val)\n",
    "      if cur.right:  cur = cur.right\n",
    "      elif cur.left: cur = cur.left\n",
    "      else: \n",
    "        rightBound.pop()\n",
    "        break\n",
    "    return leftBound + rightBound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def getleaves(rr):\n",
    "            q = deque([rr])\n",
    "            node = root\n",
    "            stack = []\n",
    "            res = []\n",
    "            while node or stack:\n",
    "                if node:\n",
    "                    stack.append(node)\n",
    "                    if not node.left and not node.right:\n",
    "                        res.append(node.val)\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = stack.pop()\n",
    "                    # res.append(node.val)\n",
    "                    node = node.right\n",
    "            return res\n",
    "\n",
    "        l = []\n",
    "        node = root.left\n",
    "        while node:\n",
    "            if node.left:\n",
    "                l.append(node.val)\n",
    "                node = node.left\n",
    "            elif node.right:\n",
    "                l.append(node.val)\n",
    "                node = node.right\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        r = []\n",
    "        node = root.right\n",
    "        while node:\n",
    "            if node.right:\n",
    "                r.append(node.val)\n",
    "                node = node.right\n",
    "            elif node.left:\n",
    "                r.append(node.val)\n",
    "                node = node.left\n",
    "            else:\n",
    "                break\n",
    "        print(l, r)\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "        return [root.val] + l + getleaves(root) + r[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        # root and left boundry\n",
    "        left_boundry = []\n",
    "        node = root.left\n",
    "        while node:\n",
    "            left_boundry.append(node.val)\n",
    "            if node.left:\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        if left_boundry:\n",
    "            left_boundry.pop()\n",
    "\n",
    "        # leaves\n",
    "        leaves = []\n",
    "        if root.left or root.right:\n",
    "            todo = []\n",
    "            cur = root\n",
    "            while cur:\n",
    "                todo.append(cur)\n",
    "                cur = cur.left\n",
    "            while todo:\n",
    "                node = todo.pop()\n",
    "                if not node.left and not node.right:\n",
    "                    leaves.append(node.val)\n",
    "                    continue\n",
    "                cur = node.right\n",
    "                while cur:\n",
    "                    todo.append(cur)\n",
    "                    cur = cur.left\n",
    "\n",
    "        # right boundry\n",
    "        right_boundry = collections.deque()\n",
    "        node = root.right\n",
    "        while node:\n",
    "            right_boundry.appendleft(node.val)\n",
    "            if node.right:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "        if right_boundry:\n",
    "            right_boundry.popleft()\n",
    "\n",
    "        return [root.val] + left_boundry + leaves + list(right_boundry)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "\n",
    "        # left boundry\n",
    "        left_boundry = []\n",
    "        node = root.left\n",
    "        while node:\n",
    "            left_boundry.append(node.val)\n",
    "            if node.left:\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        if left_boundry:\n",
    "            left_boundry.pop()\n",
    "\n",
    "        # leaves\n",
    "        leaves = []\n",
    "        stack = []\n",
    "        cur = root\n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            cur = cur.left\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if not node.left and not node.right:\n",
    "                leaves.append(node.val)\n",
    "                continue\n",
    "            cur = node.right\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "        # right boundry\n",
    "        right_boundry = collections.deque()\n",
    "        node = root.right\n",
    "        while node:\n",
    "            right_boundry.appendleft(node.val)\n",
    "            if node.right:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "        if right_boundry:\n",
    "            right_boundry.popleft()\n",
    "\n",
    "        return [root.val] + left_boundry + leaves + list(right_boundry)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def traverse(node, is_added, is_preorder):\n",
    "            nonlocal ans\n",
    "\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.left is None and node.right is None:\n",
    "                ans.append(node.val)\n",
    "                return\n",
    "\n",
    "            if is_preorder:\n",
    "                if is_added:\n",
    "                    ans.append(node.val)\n",
    "                traverse(node.left, is_added, True)\n",
    "                traverse(node.right, is_added and node.left is None, True)\n",
    "            else:\n",
    "                traverse(node.left, is_added and node.right is None, False)\n",
    "                traverse(node.right, is_added, False)\n",
    "\n",
    "                if is_added:\n",
    "                    ans.append(node.val)\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        if root is None:\n",
    "            return ans\n",
    "\n",
    "        ans.append(root.val)\n",
    "        traverse(root.left, True, True)\n",
    "        traverse(root.right, True, False)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return[]\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "        ans=[root.val]\n",
    "        left=[]\n",
    "        bottom=[]\n",
    "        right=[]\n",
    "        def dfsleft(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left or root.right:\n",
    "                left.append(root.val)\n",
    "            if root.left:\n",
    "                dfsleft(root.left)\n",
    "            else:\n",
    "                dfsleft(root.right)\n",
    "        def dfsbottom(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                bottom.append(root.val)\n",
    "            else:\n",
    "                dfsbottom(root.left)\n",
    "                dfsbottom(root.right)\n",
    "        def dfsright(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left or root.right:\n",
    "                right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsright(root.right)\n",
    "                else:\n",
    "                    dfsright(root.left)\n",
    "        dfsleft(root.left)\n",
    "        dfsbottom(root)\n",
    "        dfsright(root.right)\n",
    "        return [root.val]+left+bottom+right[::-1]        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        # 左边界\n",
    "        def dfsleft(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 忽略叶节点\n",
    "                return\n",
    "            ans.append(r.val)\n",
    "            if r.left is not None:\n",
    "                dfsleft(r.left)\n",
    "            elif r.right is not None and r != root:\n",
    "                dfsleft(r.right)\n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        left = []\n",
    "        right = []\n",
    "        res = []\n",
    "        def dfs_left(node):\n",
    "            while node:\n",
    "                left.append(node.val)\n",
    "                if not node.left:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = node.left\n",
    "\n",
    "        def dfs_right(node):\n",
    "            while node:\n",
    "                right.append(node.val)\n",
    "                if not node.right:\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = node.right\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                res.append(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs_left(root)\n",
    "        dfs_right(root)\n",
    "        dfs(root)\n",
    "\n",
    "        if not root.left and root.right:\n",
    "            return [root.val] + res + right[1:-1][::-1]\n",
    "        elif root.left and not root.right:\n",
    "            return left + res[1:]\n",
    "        elif root.left and root.right:\n",
    "            return left + res[1:] + right[1:-1][::-1]\n",
    "        else:\n",
    "            return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def _left(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return\n",
    "            ans.append(node.val)\n",
    "            if node.left:\n",
    "                _left(node.left)\n",
    "            elif node.right and node != root:\n",
    "                _left(node.right)\n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        _left(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        leaf = []\n",
    "        left = [root.val]\n",
    "        right = []\n",
    "        def pre(root,sign):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left == None and  root.right == None:\n",
    "                leaf.append(root.val)\n",
    "                return\n",
    "            #寻找左边界\n",
    "            if sign == 1:\n",
    "                left.append(root.val)\n",
    "                if not root.left:\n",
    "                    if root.right:\n",
    "                        pre(root.right,sign)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        pre(root.left, sign)\n",
    "                    #左边界节点的右子树跳转到常规先序遍历，寻找其叶子节点\n",
    "                    if root.right:\n",
    "                        pre(root.right,3)\n",
    "            if sign == 2:\n",
    "                right.append(root.val)\n",
    "                if not root.right:\n",
    "                    if root.left:\n",
    "                        pre(root.left,sign)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        pre(root.left,3)\n",
    "                    if root.right:\n",
    "                        pre(root.right,sign)\n",
    "            #非边界节点，先序遍历寻找叶子节点\n",
    "            if sign == 3:\n",
    "                pre(root.left,sign)\n",
    "                pre(root.right,sign)\n",
    "        pre(root.left,1)\n",
    "        pre(root.right,2)\n",
    "        for i in leaf:\n",
    "            left.append(i)\n",
    "        while right:\n",
    "            left.append(right.pop())\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "#         if root and not root.left and not root.right: return [root.val]\n",
    "#         left =[]\n",
    "#         bottom =[]\n",
    "#         right = []\n",
    "#         def dfsleft(root):\n",
    "#             if root and (root.left or root.right):\n",
    "#                 left.append(root.val)\n",
    "#                 if root.left:\n",
    "#                     dfsleft(root.left)\n",
    "#                 else:\n",
    "#                     dfsleft(root.right)\n",
    "#         def dfsbottom(root):\n",
    "#             if root :\n",
    "#                 if not root.left and not root.right:\n",
    "#                     bottom.append(root.val)\n",
    "#                 else:\n",
    "#                     dfsbottom(root.left)\n",
    "#                     dfsbottom(root.right)\n",
    "#         def dfsright(root):\n",
    "#             if root and (root.left or root.right):\n",
    "#                 right.append(root.val)\n",
    "#                 if root.left:\n",
    "#                     dfsright(root.left)\n",
    "#                 else:\n",
    "#                     dfsright(root.right)\n",
    "#         dfsleft(root.left)\n",
    "#         dfsbottom(root)\n",
    "#         dfsright(root.right)\n",
    "#         return [root.val] + left +bottom+right[::-1]\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:\n",
    "        if root and not root.left and not root.right:return [root.val]\n",
    "        Left = []\n",
    "        Bottom = []\n",
    "        Right = []\n",
    "        # 左边界\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        # 底部叶子\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        # 右边界\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        dfsLeft(root.left)\n",
    "        dfsBottom(root)\n",
    "        dfsRight(root.right)\n",
    "        return [root.val] + Left + Bottom + Right[::-1]\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # left: self left right\n",
    "        # right: left right self\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        left = []\n",
    "        bottom = []\n",
    "        right = []\n",
    "        def go_left(node):\n",
    "            if node and (node.left or node.right):\n",
    "                left.append(node.val)\n",
    "                if node.left:\n",
    "                    go_left(node.left)\n",
    "                else:\n",
    "                    go_left(node.right)\n",
    "        def go_bottom(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    bottom.append(node.val)\n",
    "                else:\n",
    "                    go_bottom(node.left)\n",
    "                    go_bottom(node.right)\n",
    "        def go_right(node):\n",
    "            if node and (node.left or node.right):\n",
    "                right.append(node.val)\n",
    "                if node.right:\n",
    "                    go_right(node.right)\n",
    "                else:\n",
    "                    go_right(node.left)\n",
    "        go_left(root.left)\n",
    "        go_bottom(root)\n",
    "        go_right(root.right)\n",
    "        return [root.val] + left + bottom + right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root: return []\n",
    "        def isleaf(root: Optional[TreeNode])->bool:\n",
    "            return not root.left and not root.right\n",
    "        def dfs(root: Optional[TreeNode])->None:\n",
    "            if not root: return None\n",
    "            if not root.left and not root.right:\n",
    "                leaf.append(root.val)\n",
    "                return None\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        left,right,leaf = [],[],[]\n",
    "        if not isleaf(root):\n",
    "            left.append(root.val)\n",
    "        tmp = root.left\n",
    "        while tmp:\n",
    "            if not isleaf(tmp):\n",
    "                left.append(tmp.val)\n",
    "            if tmp.left:\n",
    "                tmp = tmp.left\n",
    "            else:\n",
    "                tmp = tmp.right\n",
    "        tmp = root.right\n",
    "        while tmp:\n",
    "            if not isleaf(tmp):\n",
    "                right.append(tmp.val)\n",
    "            if tmp.right:\n",
    "                tmp = tmp.right\n",
    "            else:\n",
    "                tmp = tmp.left\n",
    "        right = right[::-1]\n",
    "        dfs(root)\n",
    "        return left+leaf+right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        # 左边界\n",
    "        def dfsleft(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 忽略叶节点\n",
    "                return\n",
    "            ans.append(r.val)\n",
    "            if r.left is not None:\n",
    "                dfsleft(r.left)\n",
    "            elif r.right is not None and r != root:\n",
    "                dfsleft(r.right)\n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "\n",
    "        res = [root.val]\n",
    "\n",
    "        # 左边界\n",
    "        cur = root\n",
    "        if root.left is not None:\n",
    "            while True:\n",
    "                if cur.left != None:\n",
    "                    res.append(cur.left.val)\n",
    "                    cur = cur.left\n",
    "                elif cur.right != None:\n",
    "                    res.append(cur.right.val)\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    break\n",
    "            res.pop()\n",
    "\n",
    "        # 叶节点\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            if root.left is not None:\n",
    "                dfs(root.left)\n",
    "            if root.right is not None:\n",
    "                dfs(root.right)\n",
    "            if root.left is None and root.right is None:\n",
    "                res.append(root.val)\n",
    "        if root.left is not None or root.right is not None:\n",
    "            dfs(root)\n",
    "\n",
    "        # 右节点\n",
    "        rightBoundary = []\n",
    "        if root.right is not None:\n",
    "            while True:\n",
    "                if root.right is not None:\n",
    "                    rightBoundary.append(root.right.val)\n",
    "                    root = root.right\n",
    "                elif root.left is not None:\n",
    "                    rightBoundary.append(root.left.val)\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    break\n",
    "            rightBoundary.pop()\n",
    "        # while len(rightBoundary):\n",
    "        #     res.append(rightBoundary[::-1])\n",
    "        res.extend(rightBoundary[::-1])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root.left==None and root.right==None:\n",
    "            return [root.val]\n",
    "        left_line=[]\n",
    "        def find_left(node):\n",
    "            nonlocal left_line\n",
    "            if node==None:\n",
    "                return            \n",
    "            if node.left==None and node.right==None:\n",
    "                return\n",
    "            else:\n",
    "                left_line.append(node.val)\n",
    "                if node.left:\n",
    "                    find_left(node.left)\n",
    "                else:\n",
    "                    find_left(node.right)\n",
    "\n",
    "        right_line=[]\n",
    "        def find_right(node):\n",
    "            nonlocal right_line\n",
    "            if node==None:\n",
    "                return            \n",
    "            if node.left==None and node.right==None:\n",
    "                return\n",
    "            else:\n",
    "                right_line.append(node.val)\n",
    "                if node.right:\n",
    "                    find_right(node.right)\n",
    "                else:\n",
    "                    find_right(node.left)\n",
    "\n",
    "        child_line=[]  \n",
    "        def find_child(node):\n",
    "            nonlocal child_line\n",
    "            if node==None:\n",
    "                return\n",
    "            if node.left==None and node.right==None:\n",
    "                child_line.append(node.val)\n",
    "            else:\n",
    "                find_child(node.left)\n",
    "                find_child(node.right)\n",
    "                          \n",
    "\n",
    "        root_line=[root.val]\n",
    "        find_left(root.left)\n",
    "        find_right(root.right)\n",
    "        find_child(root)\n",
    "\n",
    "        return root_line+left_line+child_line+right_line[::-1]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:\n",
    "        if root and not root.left and not root.right:return [root.val]\n",
    "        Left = []\n",
    "        Bottom = []\n",
    "        Right = []\n",
    "        # 左边界\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        # 底部叶子\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        # 右边界\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        dfsLeft(root.left)\n",
    "        dfsBottom(root)\n",
    "        dfsRight(root.right)\n",
    "\n",
    "        return [root.val] + Left + Bottom + Right[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        Left=[]\n",
    "        Right=[]\n",
    "        Bottom=[]\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        dfsLeft(root.left)\n",
    "        dfsRight(root.right)\n",
    "        dfsBottom(root)\n",
    "        return [root.val]+Left+Bottom+Right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # Time Complexity: O(n)\n",
    "        # Space Complexity: O(n)\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "\n",
    "        left = []\n",
    "        right = []\n",
    "        leaf = []\n",
    "\n",
    "        def dfs(root, is_left, is_right):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if is_left and not is_right:\n",
    "                left.append(root.val)\n",
    "            elif not is_left and is_right:\n",
    "                right.append(root.val)\n",
    "            elif not root.left and not root.right:\n",
    "                leaf.append(root.val)\n",
    "            \n",
    "            is_left_child = is_left and not root.left\n",
    "            is_right_child = is_right and not root.right\n",
    "\n",
    "            dfs(root.left, is_left, is_right_child)\n",
    "            dfs(root.right, is_left_child, is_right)\n",
    "        \n",
    "        dfs(root.left, True, False)\n",
    "        dfs(root.right, False, True)\n",
    "\n",
    "        return [root.val] + left + leaf + right[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def isLeaf(node):\n",
    "\n",
    "            return not node.left and not node.right\n",
    "        \n",
    "        def addLeaves(node):\n",
    "\n",
    "            if isLeaf(node):\n",
    "                res.append(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                addLeaves(node.left)\n",
    "            if node.right:\n",
    "                addLeaves(node.right)\n",
    "\n",
    "        if not root: return []\n",
    "        if not isLeaf(root): res.append(root.val)\n",
    "        t = root.left\n",
    "        while t:\n",
    "\n",
    "            if not isLeaf(t):\n",
    "                res.append(t.val)\n",
    "\n",
    "            if t.left:\n",
    "                t = t.left\n",
    "            else:\n",
    "                t = t.right\n",
    "\n",
    "        addLeaves(root)\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        t = root.right\n",
    "\n",
    "        while t:\n",
    "            if not isLeaf(t):\n",
    "                stack.append(t.val)\n",
    "            \n",
    "            if t.right:\n",
    "                t = t.right\n",
    "            else:\n",
    "                t = t.left\n",
    "\n",
    "        \n",
    "        res += stack[::-1]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right:return [root.val]\n",
    "        Left = []\n",
    "        Bottom = []\n",
    "        Right = []\n",
    "        # 左边界\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        # 底部叶子\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        # 右边界\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        dfsLeft(root.left)\n",
    "        dfsBottom(root)\n",
    "        dfsRight(root.right)\n",
    "        return [root.val] + Left + Bottom + Right[::-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "\n",
    "        def getLeftBound(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            if root.left:\n",
    "                return [root.val] + getLeftBound(root.left)\n",
    "            if root.right:\n",
    "                return [root.val] + getLeftBound(root.right)\n",
    "            return []\n",
    "        \n",
    "        def getRightBound(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            if root.right:\n",
    "                return [root.val] + getRightBound(root.right)\n",
    "            if root.left:\n",
    "                return [root.val] + getRightBound(root.left)\n",
    "            return []\n",
    "\n",
    "        leafs = []\n",
    "\n",
    "        def getLeaf(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                leafs.append(root.val)\n",
    "            else:\n",
    "                getLeaf(root.left)\n",
    "                getLeaf(root.right)\n",
    "\n",
    "        if not root or (not root.left and not root.right):\n",
    "            pass\n",
    "        else:\n",
    "            getLeaf(root)\n",
    "        return [root.val] + getLeftBound(root.left) + leafs + getRightBound(root.right)[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        # 左边界\n",
    "        def dfsleft(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 忽略叶节点\n",
    "                return\n",
    "            ans.append(r.val)\n",
    "            if r.left is not None:\n",
    "                dfsleft(r.left)\n",
    "            elif r.right is not None and r != root:\n",
    "                dfsleft(r.right)\n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:\n",
    "        if root and not root.left and not root.right:return [root.val]\n",
    "        Left = []\n",
    "        Bottom = []\n",
    "        Right = []\n",
    "        # 左边界\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        # 底部叶子\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        # 右边界\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        dfsLeft(root.left)\n",
    "        dfsBottom(root)\n",
    "        dfsRight(root.right)\n",
    "        return [root.val] + Left + Bottom + Right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = [root.val]\n",
    "        def leftMost(node):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            res.append(node.val)\n",
    "            if node.left:\n",
    "                leftMost(node.left)\n",
    "            else:\n",
    "                leftMost(node.right)\n",
    "\n",
    "        def rightMost(node):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            if node.right:\n",
    "                rightMost(node.right)\n",
    "            else:\n",
    "                rightMost(node.left)\n",
    "            res.append(node.val)\n",
    "        \n",
    "        def children(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right and node != root:\n",
    "                res.append(node.val)\n",
    "            children(node.left)\n",
    "            children(node.right)\n",
    "        \n",
    "        leftMost(root.left)\n",
    "        children(root)\n",
    "        rightMost(root.right)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # left: self left right\n",
    "        # right: left right self\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        left = []\n",
    "        bottom = []\n",
    "        right = []\n",
    "        def go_left(node):\n",
    "            if node and (node.left or node.right):\n",
    "                left.append(node.val)\n",
    "                if node.left:\n",
    "                    go_left(node.left)\n",
    "                else:\n",
    "                    go_left(node.right)\n",
    "        def go_bottom(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    bottom.append(node.val)\n",
    "                else:\n",
    "                    go_bottom(node.left)\n",
    "                    go_bottom(node.right)\n",
    "        def go_right(node):\n",
    "            if node and (node.left or node.right):\n",
    "                right.append(node.val)\n",
    "                if node.right:\n",
    "                    go_right(node.right)\n",
    "                else:\n",
    "                    go_right(node.left)\n",
    "        go_left(root.left)\n",
    "        go_bottom(root)\n",
    "        go_right(root.right)\n",
    "        return [root.val] + left + bottom + right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        left_bound = []\n",
    "        leaves = []\n",
    "        right_bound = []\n",
    "        \n",
    "        # find left bound\n",
    "        if root.left:\n",
    "            node = root.left\n",
    "            while node.left or node.right:\n",
    "                if node.left:\n",
    "                    left_bound.append(node.val)\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    left_bound.append(node.val)\n",
    "                    node = node.right\n",
    "        # find right bound\n",
    "        if root.right:\n",
    "            node = root.right\n",
    "            while node.right or node.left:\n",
    "                if node.right:\n",
    "                    right_bound.append(node.val)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    right_bound.append(node.val)\n",
    "                    node = node.left\n",
    "        # find leaves\n",
    "        def findLeaves(node):\n",
    "            nonlocal leaves\n",
    "            if not node.left and not node.right:\n",
    "                leaves.append(node.val)\n",
    "            if node.left:\n",
    "                findLeaves(node.left)\n",
    "            if node.right:\n",
    "                findLeaves(node.right)\n",
    "        if root.left or root.right:\n",
    "            findLeaves(root)\n",
    "\n",
    "        return [root.val] + left_bound + leaves + right_bound[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        left =[]\n",
    "        bottom =[]\n",
    "        right = []\n",
    "        #左边界\n",
    "        def dfsleft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsleft(root.left)\n",
    "                else:\n",
    "                    dfsleft(root.right)\n",
    "        #底部叶子节点\n",
    "        def dfsbottom(root):\n",
    "            if root :\n",
    "                if not root.left and not root.right:\n",
    "                    bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsbottom(root.left)\n",
    "                    dfsbottom(root.right)\n",
    "        #右节点\n",
    "        def dfsright(root):\n",
    "            if root and (root.left or root.right):\n",
    "                right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsright(root.right)\n",
    "                else:\n",
    "                    dfsright(root.left)\n",
    "        dfsleft(root.left)\n",
    "        dfsbottom(root)\n",
    "        dfsright(root.right)\n",
    "        return [root.val] + left +bottom+right[::-1]\n",
    "        \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        result = list()\n",
    "        if root is None:\n",
    "            return result\n",
    "        origin_root = root\n",
    "\n",
    "        def dfsleft(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                return\n",
    "            result.append(root.val)\n",
    "            if root.left is not None:\n",
    "                dfsleft(root.left)\n",
    "            elif root.right is not None and root != origin_root:\n",
    "                dfsleft(root.right)\n",
    "        \n",
    "        def dfsright(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                return\n",
    "            if root.right is not None:\n",
    "                dfsright(root.right)\n",
    "            elif root.left is not None and root != origin_root:\n",
    "                dfsright(root.left)\n",
    "            if root != origin_root:\n",
    "                result.append(root.val)\n",
    "        \n",
    "        def dfsleave(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                result.append(root.val)\n",
    "            else:\n",
    "                if root.left is not None:\n",
    "                    dfsleave(root.left)\n",
    "                if root.right is not None:\n",
    "                    dfsleave(root.right)\n",
    "        \n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = [root.val]\n",
    "        \n",
    "        def left_edge(node: Optional[TreeNode]):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans.append(node.val)\n",
    "            if node.left:\n",
    "                left_edge(node.left)\n",
    "            elif node.right:\n",
    "                left_edge(node.right)\n",
    "        \n",
    "        def bottom(node: Optional[TreeNode]):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            bottom(node.left)\n",
    "            bottom(node.right)\n",
    "            if not node.left and not node.right:\n",
    "                ans.append(node.val)\n",
    "                \n",
    "        def right_edge(node: Optional[TreeNode]):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            if node.right:\n",
    "                right_edge(node.right)\n",
    "            elif node.left:\n",
    "                right_edge(node.left)\n",
    "            nonlocal ans\n",
    "            ans.append(node.val)\n",
    "        \n",
    "        left_edge(root.left)\n",
    "        if root.left or root.right:\n",
    "            bottom(root)\n",
    "        right_edge(root.right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        curr = root.left\n",
    "        left = []\n",
    "        left.append(root.val)\n",
    "        while curr:\n",
    "            if curr.left or curr.right:\n",
    "                left.append(curr.val)\n",
    "            curr = curr.left if curr.left else curr.right\n",
    "        curr = root.right\n",
    "        right = []\n",
    "        while curr:\n",
    "            if curr.right or curr.left:\n",
    "                right.append(curr.val)\n",
    "            curr = curr.right if curr.right else curr.left\n",
    "        right.reverse()\n",
    "        leaves = []\n",
    "        def traverse(curr: TreeNode):\n",
    "            if not curr:\n",
    "                return\n",
    "            if not curr.left and not curr.right:\n",
    "                leaves.append(curr.val)\n",
    "            traverse(curr.left)\n",
    "            traverse(curr.right)\n",
    "        if root.left or root.right:\n",
    "            traverse(root)\n",
    "        return left + leaves + right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        leftbound = []\n",
    "        leaves = []\n",
    "        rightbound = []\n",
    "        if root and not root.left and not root.right:\n",
    "            return [root.val]\n",
    "\n",
    "        def dfsleft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                leftbound.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsleft(root.left)\n",
    "                else:\n",
    "                    dfsleft(root.right)\n",
    "        \n",
    "        def dfsright(root):\n",
    "            if root and (root.left or root.right):\n",
    "                rightbound.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsright(root.right)\n",
    "                else:\n",
    "                    dfsright(root.left)\n",
    "\n",
    "        def dfsleaves(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    leaves.append(root.val)\n",
    "                else:\n",
    "                    dfsleaves(root.left)\n",
    "                    dfsleaves(root.right)\n",
    "        \n",
    "        dfsleft(root.left)\n",
    "        dfsleaves(root)\n",
    "        dfsright(root.right)\n",
    "        return [root.val] + leftbound + leaves + rightbound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root.left is None and root.right is None:\n",
    "            return [root.val]\n",
    "\n",
    "        self.leaf = []\n",
    "        self.left_border = []\n",
    "        self.right_border = []\n",
    "\n",
    "        def find_leaf(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.left is None and node.right is None:\n",
    "                self.leaf.append(node.val)\n",
    "            find_leaf(node.left)\n",
    "            find_leaf(node.right)\n",
    "\n",
    "        def find_left_border(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return\n",
    "            self.left_border.append(node.val)\n",
    "            if node.left is None:\n",
    "                find_left_border(node.right)\n",
    "            else:\n",
    "                find_left_border(node.left)\n",
    "\n",
    "        def find_right_border(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return\n",
    "            self.right_border.append(node.val)\n",
    "            if node.right is None:\n",
    "                find_right_border(node.left)\n",
    "            else:\n",
    "                find_right_border(node.right)\n",
    "\n",
    "        find_leaf(root)\n",
    "        if root.left:\n",
    "            find_left_border(root.left)\n",
    "        if root.right:\n",
    "            find_right_border(root.right)\n",
    "\n",
    "        print(self.left_border)\n",
    "        print(self.right_border)\n",
    "        print(self.leaf)\n",
    "\n",
    "        res = [root.val] + self.left_border + self.leaf + self.right_border[::-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def isLeaf(node):\n",
    "            return not node.left and not node.right\n",
    "        \n",
    "        def addLeaves(ans, node):\n",
    "            if isLeaf(node):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    addLeaves(ans, node.left)\n",
    "                if node.right:\n",
    "                    addLeaves(ans, node.right)\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        if not root:\n",
    "            return ans\n",
    "        \n",
    "        if not isLeaf(root):\n",
    "            ans.append(root.val)\n",
    "        \n",
    "        node = root.left\n",
    "        while node:\n",
    "            if not isLeaf(node):\n",
    "                ans.append(node.val)\n",
    "            if node.left:\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        addLeaves(ans, root)\n",
    "\n",
    "        stack = []\n",
    "        node = root.right\n",
    "        while node:\n",
    "            if not isLeaf(node):\n",
    "                stack.append(node.val)\n",
    "            if node.right:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ret=[root.val]\n",
    "        ret2=[]\n",
    "        def dfs_l(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                return\n",
    "            ret.append(root.val)\n",
    "            if root.left!=None:\n",
    "                dfs_l(root.left)\n",
    "            else:\n",
    "                if root.right!=None:\n",
    "                    dfs_l(root.right)\n",
    "        def dfs_r(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                return\n",
    "            ret2.append(root.val)\n",
    "            if root.right!=None:\n",
    "                dfs_r(root.right)\n",
    "            else:\n",
    "                if root.left!=None:\n",
    "                    dfs_r(root.left)\n",
    "        def dfs_leaf(root):\n",
    "            if root==None:\n",
    "                return\n",
    "            if root.left==None and root.right==None:\n",
    "                ret.append(root.val)\n",
    "                return\n",
    "            dfs_leaf(root.left)\n",
    "            dfs_leaf(root.right)\n",
    "        if root.left!=None:\n",
    "            dfs_l(root.left)\n",
    "        if root.right!=None:\n",
    "            dfs_r(root.right)\n",
    "        ret2.reverse()\n",
    "        if root.left!=None or root.right!=None:\n",
    "            dfs_leaf(root)\n",
    "        ret+=ret2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # Time Complexity: O(n)\n",
    "        # Space Complexity: O(n)\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "            \n",
    "        left = []\n",
    "        right = []\n",
    "        leaf = []\n",
    "\n",
    "        def dfs_left(root):\n",
    "            if root and (root.left or root.right):\n",
    "                left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfs_left(root.left)\n",
    "                else:\n",
    "                    dfs_left(root.right)\n",
    "\n",
    "        def dfs_right(root):\n",
    "            if root and (root.left or root.right):\n",
    "                right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfs_right(root.right)\n",
    "                else:\n",
    "                    dfs_right(root.left)\n",
    "\n",
    "        def dfs_leaf(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.right and not root.left:\n",
    "                leaf.append(root.val)\n",
    "            else:\n",
    "                dfs_leaf(root.left)\n",
    "                dfs_leaf(root.right)\n",
    "        \n",
    "        dfs_left(root.left)\n",
    "        dfs_leaf(root)\n",
    "        dfs_right(root.right)\n",
    "\n",
    "        return [root.val] + left + leaf + right[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root.left is None and root.right is None:\n",
    "            return [root.val]\n",
    "        def left(p):\n",
    "            if p is None:\n",
    "                return []\n",
    "            if p.left:\n",
    "                return [p.val]+left(p.left)\n",
    "            elif p.right:\n",
    "                return [p.val]+left(p.right)\n",
    "            else:\n",
    "                if p in que: return []\n",
    "                else: return [p.val]\n",
    "        def right(p):\n",
    "            if p is None: return []\n",
    "            if p.right: return [p.val]+right(p.right)\n",
    "            elif p.left: return [p.val]+right(p.left)\n",
    "            else:\n",
    "                if p in que: return []\n",
    "                else: return [p.val]\n",
    "        if root is None: return []\n",
    "        def yz(p):\n",
    "            if p is None:\n",
    "                return\n",
    "            if p.left is None and p.right is None:\n",
    "                lt3.append(p.val)\n",
    "                que.append(p)\n",
    "            if p.left:\n",
    "                yz(p.left)\n",
    "            if p.right:\n",
    "                yz(p.right)\n",
    "      \n",
    "      \n",
    "        lt3=list()\n",
    "        que=list()\n",
    "        yz(root)\n",
    "        \n",
    "        lt1=left(root.left)\n",
    "        lt2=right(root.right)\n",
    "        lt2.reverse()\n",
    "        print(lt1,lt2,lt3)\n",
    "        return [root.val]+lt1+lt3+lt2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    left_boundary = []\n",
    "    right_boundary = []\n",
    "    leaves = []\n",
    "    \n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # print(self.leaves)\n",
    "        self._traverse(root.left, True, False)\n",
    "        self._traverse(root.right, False, True)\n",
    "\n",
    "        self.right_boundary.reverse()\n",
    "\n",
    "        res = [root.val] + self.left_boundary + self.leaves + self.right_boundary\n",
    "\n",
    "        self.left_boundary.clear()\n",
    "        self.leaves.clear()\n",
    "        self.right_boundary.clear()\n",
    "\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def _traverse(self, root, is_left_boundary, is_right_boundary):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            # print(\"Find a leaf \")\n",
    "            # print(root.val)\n",
    "            self.leaves.append(root.val)\n",
    "            return\n",
    "\n",
    "        if is_left_boundary:\n",
    "            self.left_boundary.append(root.val)\n",
    "\n",
    "        if is_right_boundary:\n",
    "            self.right_boundary.append(root.val)\n",
    "            \n",
    "        self._traverse(\n",
    "            root.left, \n",
    "            True if is_left_boundary and root.left is not None else False, \n",
    "            True if is_right_boundary and root.right is None else False,\n",
    "        )  \n",
    "\n",
    "        self._traverse(\n",
    "            root.right, \n",
    "            True if is_left_boundary and root.left is None else False, \n",
    "            True if is_right_boundary and root.right is not None else False,\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root.left is None and root.right is None:\n",
    "            return [root.val]\n",
    "        left_bound = []\n",
    "        right_bound = []\n",
    "        leaf = []\n",
    "        node = root.left\n",
    "        while node is not None:\n",
    "            if node.left is not None:\n",
    "                left_bound.append(node.val)\n",
    "            elif node.right is not None:\n",
    "                left_bound.append(node.val)\n",
    "                node = node.right\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "            node = node.left\n",
    "        node = root.right\n",
    "        while node is not None:\n",
    "            if node.right is not None:\n",
    "                right_bound.append(node.val)\n",
    "            elif node.left is not None:\n",
    "                right_bound.append(node.val)\n",
    "                node = node.left\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "            node = node.right\n",
    "        def addleaves(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.left is None and node.right is None:\n",
    "                leaf.append(node.val)\n",
    "                return\n",
    "            addleaves(node.left)\n",
    "            addleaves(node.right)\n",
    "        addleaves(root)\n",
    "        return [root.val] + left_bound + leaf + right_bound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = [root.val]\n",
    "        \n",
    "        def left_edge(node: Optional[TreeNode]):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans.append(node.val)\n",
    "            if node.left:\n",
    "                left_edge(node.left)\n",
    "            elif node.right:\n",
    "                left_edge(node.right)\n",
    "        \n",
    "        def bottom(node: Optional[TreeNode]):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            bottom(node.left)\n",
    "            bottom(node.right)\n",
    "            if not node.left and not node.right:\n",
    "                ans.append(node.val)\n",
    "                \n",
    "        def right_edge(node: Optional[TreeNode]):\n",
    "            if not node or (not node.left and not node.right):\n",
    "                return\n",
    "            if node.right:\n",
    "                right_edge(node.right)\n",
    "            elif node.left:\n",
    "                right_edge(node.left)\n",
    "            nonlocal ans\n",
    "            ans.append(node.val)\n",
    "        \n",
    "        left_edge(root.left)\n",
    "        if root.left or root.right:\n",
    "            bottom(root)\n",
    "        right_edge(root.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans= []\n",
    "        # left ridge\n",
    "        def dfsleft(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return \n",
    "            ans.append(r.val)\n",
    "            if r.left is not None:\n",
    "                dfsleft(r.left)\n",
    "            elif r.right is not None and r!= root:\n",
    "                dfsleft(r.right)\n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "\n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        left = []\n",
    "        bottom = []\n",
    "        right = []\n",
    "        def dfs_left(root):\n",
    "            if root and (root.left or root.right):\n",
    "                left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfs_left(root.left)\n",
    "                else:\n",
    "                    dfs_left(root.right)\n",
    "        \n",
    "        def dfs_bottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    bottom.append(root.val)\n",
    "                else:\n",
    "                    dfs_bottom(root.left)\n",
    "                    dfs_bottom(root.right)\n",
    "        \n",
    "        def dfs_right(root):\n",
    "            if root and (root.left or root.right):\n",
    "                right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfs_right(root.right)\n",
    "                else:\n",
    "                    dfs_right(root.left)\n",
    "        \n",
    "        dfs_left(root.left)\n",
    "        dfs_bottom(root)\n",
    "        dfs_right(root.right)\n",
    "        return [root.val] + left + bottom + right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(node, is_left, is_right):\n",
    "            # 1. none\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            # 2. leaf\n",
    "            if not node.left and not node.right:\n",
    "                leaves.append(node.val)\n",
    "                return\n",
    "\n",
    "            # 3. boundary\n",
    "            if is_left:\n",
    "                left_bound.append(node.val)\n",
    "                is_left = False if node.left else True\n",
    "                dfs(node.left, True, False)\n",
    "                dfs(node.right, is_left, False)\n",
    "            elif is_right:\n",
    "                right_bound.append(node.val)\n",
    "                is_right = False if node.right else True\n",
    "                dfs(node.left, False, is_right)\n",
    "                dfs(node.right, False, True)\n",
    "            else:\n",
    "                dfs(node.left, False, False)\n",
    "                dfs(node.right, False, False)\n",
    "\n",
    "        left_bound, leaves, right_bound = [root.val], [], []\n",
    "        dfs(root.left, True, False)\n",
    "        dfs(root.right, False, True)\n",
    "        return left_bound + leaves + right_bound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right: return [root.val]\n",
    "        left, bottom, right = [], [], []\n",
    "        def dfsleft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsleft(root.left)\n",
    "                else:\n",
    "                    dfsleft(root.right)\n",
    "        \n",
    "        def dfsbottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsbottom(root.left)\n",
    "                    dfsbottom(root.right)\n",
    "        \n",
    "        def dfsright(root):\n",
    "            if root and (root.left or root.right):\n",
    "                right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsright(root.right)\n",
    "                else:\n",
    "                    dfsright(root.left)\n",
    "        \n",
    "        dfsleft(root.left)\n",
    "        dfsbottom(root)\n",
    "        dfsright(root.right)\n",
    "        return [root.val] + left + bottom + right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    #关键是理解题目的要求：划分为四部分，根节点，左边界，叶节点，和右边界\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        # 左边界\n",
    "        def dfsleft(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 忽略叶子节点\n",
    "                return\n",
    "            ans.append(r.val)\n",
    "            if r.left is not None:\n",
    "                dfsleft(r.left)\n",
    "            elif r.right is not None and r != root:\n",
    "                dfsleft(r.right)\n",
    "        \n",
    "        # 叶节点\n",
    "        def dfsleave(r):\n",
    "            if r.left is None and r.right is None:\n",
    "            # 这里要注意，一个左边界点不存在左节点时其右子节点是左边界，但是跟不包括在左边界中\n",
    "                ans.append(r.val)\n",
    "            # 就是要从左到右保存叶节点\n",
    "            else:\n",
    "                if r.left is not None:\n",
    "                    dfsleave(r.left)\n",
    "                if r.right is not None:\n",
    "                    dfsleave(r.right)\n",
    "        \n",
    "        # 右边界\n",
    "        def dfsright(r):\n",
    "            if r.left is None and r.right is None:\n",
    "                return\n",
    "            if r.right is not None:\n",
    "                dfsright(r.right)\n",
    "            elif r.left is not None and r != root:\n",
    "                dfsright(r.left)\n",
    "            if r != root:\n",
    "            # 忽略根节点，已经记录在左边界中了\n",
    "                ans.append(r.val)\n",
    "            # 放最后，倒叙存入\n",
    "        dfsleft(root)\n",
    "        dfsleave(root)\n",
    "        dfsright(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        leaf = []\n",
    "        left = [root.val]\n",
    "        right = collections.deque()\n",
    "        def pre(root,sign):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left == None and  root.right == None:\n",
    "                leaf.append(root.val)\n",
    "                return\n",
    "            if sign == 1:\n",
    "                left.append(root.val)\n",
    "                if not root.left:\n",
    "                    if root.right:\n",
    "                        pre(root.right,sign)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        pre(root.left, sign)\n",
    "                    if root.right:\n",
    "                        pre(root.right,3)\n",
    "            if sign == 2:\n",
    "                right.appendleft(root.val)\n",
    "                if not root.right:\n",
    "                    if root.left:\n",
    "                        pre(root.left,sign)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        pre(root.left,3)\n",
    "                    if root.right:\n",
    "                        pre(root.right,sign)\n",
    "            if sign == 3:\n",
    "                pre(root.left,sign)\n",
    "                pre(root.right,sign)\n",
    "        pre(root.left,1)\n",
    "        pre(root.right,2)\n",
    "        right = list(right)\n",
    "        return left+leaf+right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right:return [root.val]\n",
    "        Left =[]\n",
    "        Bottom = []\n",
    "        Right = []\n",
    "        # 左边界\n",
    "        def dfsLeft(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Left.append(root.val)\n",
    "                if root.left:\n",
    "                    dfsLeft(root.left)\n",
    "                else:\n",
    "                    dfsLeft(root.right)\n",
    "        # 底部叶子\n",
    "        def dfsBottom(root):\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    Bottom.append(root.val)\n",
    "                else:\n",
    "                    dfsBottom(root.left)\n",
    "                    dfsBottom(root.right)\n",
    "        # 右边界\n",
    "        def dfsRight(root):\n",
    "            if root and (root.left or root.right):\n",
    "                Right.append(root.val)\n",
    "                if root.right:\n",
    "                    dfsRight(root.right)\n",
    "                else:\n",
    "                    dfsRight(root.left)\n",
    "        dfsLeft(root.left)\n",
    "        dfsBottom(root)\n",
    "        dfsRight(root.right)\n",
    "        return [root.val] + Left + Bottom + Right[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root and not root.left and not root.right:\n",
    "            return [root.val]\n",
    "            \n",
    "        left_bound = []\n",
    "        right_bound = []\n",
    "        leaf = []\n",
    "\n",
    "        def dfsLeft(node):\n",
    "            if node and (node.left or node.right):\n",
    "                left_bound.append(node.val)\n",
    "                if node.left:\n",
    "                    dfsLeft(node.left)\n",
    "                else:\n",
    "                    dfsLeft(node.right)\n",
    "\n",
    "        def dfsLeaf(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    leaf.append(node.val)\n",
    "                else:\n",
    "                    dfsLeaf(node.left)\n",
    "                    dfsLeaf(node.right)\n",
    "        \n",
    "        def dfsRight(node):\n",
    "            if node and (node.left or node.right):\n",
    "                right_bound.append(node.val)\n",
    "                if node.right:\n",
    "                    dfsRight(node.right)\n",
    "                else:\n",
    "                    dfsRight(node.left)\n",
    "        \n",
    "        dfsLeft(root.left)\n",
    "        dfsLeaf(root)\n",
    "        dfsRight(root.right)\n",
    "\n",
    "        return [root.val] + left_bound + leaf + right_bound[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    left_boundary = []\n",
    "    right_boundary = []\n",
    "    leaves = []\n",
    "    \n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # print(self.leaves)\n",
    "        self._traverse(root.left, True, False)\n",
    "        self._traverse(root.right, False, True)\n",
    "\n",
    "        self.right_boundary.reverse()\n",
    "\n",
    "        res = [root.val] + self.left_boundary + self.leaves + self.right_boundary\n",
    "\n",
    "        self.left_boundary.clear()\n",
    "        self.leaves.clear()\n",
    "        self.right_boundary.clear()\n",
    "\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def _traverse(self, root, is_left_boundary, is_right_boundary):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            print(\"Find a leaf \")\n",
    "            print(root.val)\n",
    "            self.leaves.append(root.val)\n",
    "            return\n",
    "\n",
    "        if is_left_boundary:\n",
    "            self.left_boundary.append(root.val)\n",
    "\n",
    "        if is_right_boundary:\n",
    "            self.right_boundary.append(root.val)\n",
    "            \n",
    "        self._traverse(\n",
    "            root.left, \n",
    "            True if is_left_boundary and root.left is not None else False, \n",
    "            True if is_right_boundary and root.right is None else False,\n",
    "        )  \n",
    "\n",
    "        self._traverse(\n",
    "            root.right, \n",
    "            True if is_left_boundary and root.left is None else False, \n",
    "            True if is_right_boundary and root.right is not None else False,\n",
    "        )\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
